package com.chapter5.string;

import java.util.Random;

/**
 * 
 * @ClassName: ThreeWayRadixQuickSort
 * @Description: 三项字符串快速排序
 * @author minjun
 * @date 2015年3月18日 下午11:25:25
 * 
 */
public class ThreeWayRadixQuickSort {

	public static void sort(String[] a) {
		shuffle(a);
		sort(a, 0, a.length - 1, 0);
	}

	private static void sort(String[] a, int start, int end, int pos) {
		if (end <= start)
			return;
		int s = start;
		int i = start + 1;
		int j = end;
		int d = charAt(a[start], pos);
		while (i <= j) {
			int t = charAt(a[i], pos);
			if (t < d) {
				exchange(a, i++, s++);
			} else if (t > d) {
				exchange(a, i, j--);
			} else {
				i++;
			}
		}

		sort(a, start, s - 1, pos);
		if (d >= 0)
			sort(a, s, j, pos + 1);
		sort(a, j + 1, end, pos);
	}

	/**
	 * 
	 * @Title: exchange
	 * @Description: 交换元素
	 * @param @param a
	 * @param @param i
	 * @param @param j 设定文件
	 * @return void 返回类型
	 * @throws
	 */
	private static void exchange(String[] a, int i, int j) {
		String temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	/**
	 * 
	 * @Title: shuffle
	 * @Description: 排序
	 * @param @param a 设定文件
	 * @return void 返回类型
	 * @throws
	 */
	private static void shuffle(String[] a) {
		Random r = new Random();
		for (int i = 0; i < a.length; i++) {
			exchange(a, i, r.nextInt(i + 1));
		}
	}

	private static int charAt(String s, int pos) {
		return pos > (s.length()-1) ? -1 : s.charAt(pos);
	}
}
